package gold.digger;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC380 {
    public long startExecuteTime = System.currentTimeMillis();


    private class ListNode {
        public int val;
        public ListNode pre;
        public ListNode next;

        public ListNode(int x) {
            val = x;
        }
    }

    class RandomizedSet {

        /**
         * Initialize your data structure here.
         */

        public ListNode tail;
        public Map<Integer, ListNode> map = new HashMap<>();

        public RandomizedSet() {

        }

        /**
         * Inserts a value to the set. Returns true if the set did not already contain the specified element.
         */
        public boolean insert(int val) {
            if (tail == null) {
                tail = new ListNode(val);
                map.put(val, tail);
                return true;
            }

            if (map.containsKey(val)) return false;

            ListNode cur = new ListNode(val);
            tail.next = cur;
            cur.pre = tail;
            tail = cur;
            map.put(val, tail);
            return true;
        }

        /**
         * Removes a value from the set. Returns true if the set contained the specified element.
         */
        public boolean remove(int val) {
            ListNode cur = map.get(val);
            if (null == cur) return false;

            if (null != cur.pre) cur.pre.next = cur.next;
            if (null != cur.next) cur.next.pre = cur.pre;
            map.remove(val);
            return true;
        }

        /**
         * Get a random element from the set.
         */
        public int getRandom() {
            Integer[] keys = map.keySet().toArray(new Integer[0]);
            Random random = new Random();
            Integer randomKey = keys[random.nextInt(keys.length)];
            return randomKey;
        }
    }

    /**
     * Your RandomizedSet object will be instantiated and called as such:
     * RandomizedSet obj = new RandomizedSet();
     * boolean param_1 = obj.insert(val);
     * boolean param_2 = obj.remove(val);
     * int param_3 = obj.getRandom();
     */


    public void run() {
        RandomizedSet ra = new RandomizedSet();
        ra.insert(1);
        ra.remove(2);
        ra.insert(2);
        ra.getRandom();
        ra.remove(1);
        ra.insert(2);
        ra.getRandom();
    }

    public static void main(String[] args) throws Exception {
        LC380 an = new LC380();
        an.run();

        System.out.println("\nanswer total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
